The following U.S. patent applications are related to the present application and are hereby specifically incorporated by reference: patent application Ser. No. 10/114,798, entitled xe2x80x9cVIDEO DECODING SYSTEM SUPPORTING MULTIPLE STANDARDSxe2x80x9d; patent application Ser. No. 10/114,679, entitled xe2x80x9cMETHOD OF OPERATING A VIDEO DECODING SYSTEMxe2x80x9d; patent application Ser. No. 10/114,797, entitled xe2x80x9cMETHOD OF COMMUNICATING BETWEEN MODULES IN A DECODING SYSTEMxe2x80x9d; patent application Ser. No. 10/114,886, entitled xe2x80x9cMEMORY SYSTEM FOR VIDEO DECODING SYSTEMxe2x80x9d; patent application Ser. No. 10/114,619, entitled xe2x80x9cINVERSE DISCRETE COSINE TRANSFORM SUPPORTING MULTIPLE DECODING PROCESSESxe2x80x9d; and patent application Ser. No. 10/113,094, entitled xe2x80x9cRISC PROCESSOR SUPPORTING ONE OR MORE UNINTERRUPTIBLE CO-PROCESSORSxe2x80x9d; all filed on Apr. 1, 2002. The following Provisional U.S. Patent Applications are also related to the present application and are hereby specifically incorporated by reference: Provisional Patent Application No. 60/369,144, entitled xe2x80x9cVIDEO DECODING SYSTEM HAVING A PROGRAMMABLE VARIABLE LENGTH DECODERxe2x80x9d; Provisional Patent Application No. 60/369,210 entitled xe2x80x9cDMA ENGINE HAVING MULTI-LEVEL COMMAND STRUCTURExe2x80x9d; and Provisional Patent Application No. 60/369,217, entitled xe2x80x9cINVERSE QUANTIZER SUPPORTING MULTIPLE DECODING PROCESSESxe2x80x9d; all filed on Apr. 1, 2002.
The present invention relates generally to video decoding systems, and, more particularly, to variable-length decoding.
Generally, large amounts of data being compressed and decompressed for numerous reasons, including transmission, storage, retrieval, and processing use at some stage means of variable-length coding, such as Huffman coding. Huffman coding was originally disclosed by D. A. Huffman in an article xe2x80x9cA Method for the Construction of Minimum Redundancy Codesxe2x80x9d Proc. IRE, 40: 1098, 1952. Huffman coding is a widely used technique for lossless data compression that achieves compact data representation by taking advantage of the statistical characteristics of the source. The Huffman code is a prefix-free variable-length code that assures that a code is uniquely decodable. In Huffman code, no codeword is the prefix of any other codeword. The run-length processed data are often subsequently coded by variable-length coding for further data compression.
Variable-length encoding allocates codes of different lengths to different input data according to the probability of occurrence of the input data, so that statistically, more frequent input codes are allocated shorter codes than the less frequent codes. The less frequent input codes are allocated longer codes. The allocation of codes may be done either statically or adaptively. For the static case, the same output code is provided for a given input datum, no matter what block of data is being processed. For the adaptive case, output codes are assigned to input data based on a statistical analysis of a particular input block or set of blocks of data, and possibly changes from block to block (or from a set of blocks to a set of blocks).
The combination of run-length coding and Huffman coding has been adopted in most compression/decompression standards. However, every standard has its own Huffman tables and run-length definitions. In principle, a programmable decoding table could be implemented by a random access memory (RAM) unit. However, it would require a 2{circumflex over ( )}16 word RAM (if the longest length of a codeword is 16 bits) which would be very wasteful. It is much more efficient to use a content addressable memory (CAM) whose sizes are determined only by the number of codebook entries. However, if it were implemented by CAM, it would result in a circuit much larger and complicated than a circuit using only a small RAM. Thus there is a need for a simple and flexible variable-length decoder that can speedily and efficiently decode variable length codes of varying standards.
Further limitations and disadvantages of conventional and traditional approaches will become apparent to one of skill in the art through comparison of such systems with the present invention, as set forth in the remainder of the present application with reference to the drawings.
One aspect of the present invention is directed to a data decoding system having a variable-length decoder (VLD) and an external memory unit. The variable-length decoder includes an address generator and a local memory unit. The address generator receives data from the data stream and generates a memory address at which to search for a codeword match in a VLD look-up table. The local memory unit stores at least a portion of the VLD look-up table. The external memory unit is external to the variable-length decoder and stores a portion of the VLD look-up table if the VLD look-up table does not fit entirely within the local memory unit.
Another aspect of the present invention is directed to a method of decoding a variable-length code data stream. Pursuant to the method, a base memory address is set equal to a start address. Then the next n bits in the data stream are retrieved. A memory location having an address equal to the sum of the base address, plus the value of the n retrieved bits, is accessed. The memory location includes status data indicating whether a codeword from the data stream is matched with its corresponding information. Each memory location that represents a codeword match includes the corresponding information. Each memory location that does not include a codeword match includes an offset value. If a codeword is matched with its corresponding information, the corresponding information is output, the base address is set equal to the start address, and the data in the data stream is shifted by a number of the retrieved bits that correspond to the outputted information. If a codeword is not matched with its corresponding information, the base address is set according to the offset value, and the data in the data stream is shifted n bits. This process, beginning with the retrieval of the next n bits in the data stream, is iteratively repeated.
Another aspect of the present invention is directed to another method of decoding a variable-length code data stream. Pursuant to this method, a first memory element is designated a memory element to be searched. Then the next n bits in the data stream are retrieved. A designated memory location in the memory element to be searched is accessed. The memory location includes status data indicating whether a codeword from the data stream is matched with its corresponding information. Each memory location that represents a codeword match includes the corresponding information. Each memory location that does not include a codeword match includes a next-search-location indicator indicating a memory element at which to perform the next search. If a codeword is matched with its corresponding information, the corresponding information is output, the first memory element is designated the memory element to be searched, and the data in the data stream is shifted by a number of the retrieved bits that correspond to the outputted information. If a codeword is not matched with its corresponding information, the memory element indicated by the next-search indicator is designated the memory element to be searched, and the data in the data stream is shifted n bits. This process, beginning with the retrieval of the next n bits in the data stream, is iteratively repeated.
It is understood that other embodiments of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein embodiments of the invention are shown and described only by way of illustration of the best modes contemplated for carrying out the invention. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modification in various other respects, all without departing from the spirit and scope of the present invention. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive.